package xhhx.test;

public class Sort {
    // 直接插入排序 O(n^2) 空间O(1)
    public static void Insert(int[] array) {
        for (int i = 1; i < array.length; i++) {
            if (array[i] < array[i - 1]) {
                int temp = array[i];
                array[i] = array[i - 1];
                int j;
                for (j = i - 2; j >= 0 && temp < array[j]; j--) {
                    array[j + 1] = array[j];
                }
                array[j + 1] = temp;
            }
        }
    }

    //二分插入排序 O(n^2) 空间O(1)
    public static void BinaryInsert(int[] array) {
        for (int i = 1; i < array.length; i++) {
            if (array[i] < array[i - 1]) {
                int temp = array[i];
                int low = 0;
                int high = i - 1;
                while (high >= low) {
                    int mid = (low + high) / 2;
                    if (temp < array[mid])
                        high = mid - 1;
                    else
                        low = mid + 1;
                }

                int j;
                for (j = i - 1; j >= high + 1; j--) {
                    array[j + 1] = array[j];
                }
                array[j + 1] = temp;
            }
        }
    }

    private static void shellInsert(int[] array, int d) {
        for (int i = d; i < array.length; i++) {
            if (array[i] < array[i - d]) {
                int temp = array[i];
                array[i] = array[i - d];

                int j;
                for (j = i - 2 * d; j >= 0 && temp < array[j]; j -= d) {
                    array[j + d] = array[j];
                }
                array[j + d] = temp;
            }
        }
    }

    // 希尔排序 O(n^1,3) 空间O(1) 不稳定排序
    public static void ShellSort(int[] array, int[] d) {
        for (int i = 0; i < d.length; i++) {
            shellInsert(array, d[i]);
        }
    }

    // 冒泡排序 O(n^2) 空间O(1)
    public static void Bubble(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            for (int j = 0; j < array.length - i - 1; j++)
                if (array[j + 1] < array[j]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
        }
    }

    // 冒泡排序 O(n^2) 空间O(1) 优化:当有一趟没有交换时，排序结束。
    public static void Bubble2(int[] array) {
        int m = array.length;
        boolean flag = true;
        while (m > 0 && flag) {
            flag = false;
            for (int i = 1; i < m; i++) {
                if (array[i] < array[i - 1]) {
                    flag = true;
                    int temp = array[i];
                    array[i] = array[i - 1];
                    array[i - 1] = temp;
                }
            }
            m--;
        }
    }

    private static void quickSort(int[] array, int start, int end) {
        if (start >= end) {
            return;
        }
        int low = start;
        int high = end;
        int pivotKey = array[low];
        while (low < high) {
            while (low < high && array[high] >= pivotKey) {
                high--;
            }
            array[low] = array[high];

            while (low < high && array[low] <= pivotKey) {
                low++;
            }

            array[high] = array[low];
        }
        array[low] = pivotKey;

        quickSort(array, start, low - 1);
        quickSort(array, low + 1, end);


    }

    // 快速排序 O(nlog2(n)) 空间O(log2(n)) 不稳定排序
    public static void Quick(int[] array) {
        quickSort(array, 0, array.length - 1);
    }

    //选择排序 O(n^2) 空间O(1) 不稳定排序
    public static void Select(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int k = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[k]) {
                    k = j;
                }
            }

            if (array[k] != array[i]) {
                int temp = array[k];
                array[k] = array[i];
                array[i] = temp;
            }

        }
    }

    private static void Merge(int[] R, int[] T, int low, int mid, int high) {
        int i = low;
        int j = mid + 1;
        int k = low;

        while (i <= mid && j <= high) {
            if (R[i] > R[j]) {
                T[k++] = R[j++];
            } else {
                T[k++] = R[i++];
            }
        }

        while (i <= mid) {
            T[k++] = R[i++];
        }

        while (j <= high) {
            T[k++] = R[j++];
        }

    }

    private static void MSort(int[] R, int[] T, int low, int high) {
        if (low == high) {
            T[low] = R[low];
        } else {
            int[] S = new int[R.length];
            int mid = (low + high) / 2;
            MSort(R, S, low, mid);
            MSort(R, S, mid + 1, high);
            Merge(S, T, low, mid, high);
        }
    }

    // 归并排序 时间O(nlog2(n)) 空间O(n) 稳定排序
    public static void MergeSort(int[] array) {
        MSort(array, array, 0, array.length - 1);
    }

    private static void HeadAdjust(int[] array, int s, int m) {
        int rc = array[s];
        for (int j = 2 * s + 1; j <= m; j =j * 2 + 1){
            if (j<m&&array[j] < array[j+1]){
                j++;
            }
            if (rc > array[j]){
                break;
            }
            array[s] = array[j];
            s = j;
        }

        array[s] = rc;
    }

    private static void CreateHead(int[] array){
        for (int i = array.length / 2 -1; i >=0; i--){
            HeadAdjust(array, i, array.length-1);
        }
    }

    // 堆排序 时间O(nlog2(n)) 空间O(1)  不稳定，
    public static void HeadSort(int[] array){
        CreateHead(array);
        for (int i = array.length - 1; i >0;i--){
            int temp = array[0];
            array[0] = array[i];
            array[i] = temp;
            HeadAdjust(array,0, i-1);
        }
    }
}
